/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/search-a-2d-matrix
   @Language: C++
   @Datetime: 19-07-04 12:35
   */

// Method 1, Time O(mlogn) 8ms, Space O(1) 9.6MB
class Solution {
public:
	bool searchMatrix(vector<vector<int>>& matrix, int target) {
		if(matrix.size()==0 || matrix[0].size()==0) return false;
		int m=matrix.size(), n=matrix[0].size();
		for(int i=0; i<m; ++i)
			if(matrix[i][n-1]>=target)
				return binary_search(matrix[i].begin(),matrix[i].end(),target);
		return false;
	}
};

// Method 2, Time O(log(mn)) 4ms, Space O(1) 9.8MB
class Solution {
public:
	bool searchMatrix(vector<vector<int>>& matrix, int target) {
		if(matrix.size()==0 || matrix[0].size()==0) return false;
		int m=matrix.size(), n=matrix[0].size(), begin=0;
		for(int end=m; begin<end;){
			int row=(begin+end)/2;
			if(matrix[row][n-1]==target) return true;
			else if(matrix[row][n-1]>target) end=row;
			else begin=row+1;
		}
		return begin==m?false:binary_search(matrix[begin].begin(),matrix[begin].end(),target);
	}
};
